def mul(a,b):
    n,m=len(a),len(a[0])
    _m,k=len(b),len(b[0])

    # a的列 ！= b的行 ，不能进行矩阵乘法
    if m!=_m:
        return False
    # 结果矩阵为 n行k列
    ans=[[0]*k for _ in range(n)]
    # 遍历行
    for i in range(n):
        # 遍历列
        for j in range(k):
            # 遍历 m
            for z in range(m):
                # 求ans[i][j]
                ans[i][j]+=a[i][z]*b[z][j]%MOD
    return ans

def ksm(a,b):
    n=len(a)
    # 构建单位矩阵，对角线值为1，其他值为0
    ans=[[1 if i==j else 0 for j in range(n)] for i in range(n)]
    while b:
        # 求出二进制中为1的每一位
        if b&1:
            # 进行矩阵乘法
            ans=mul(ans,a)
        b>>=1
        # 矩阵 自乘
        a=mul(a,a)
    return ans

t=int(input())
MOD=10**9+7

for _ in range(t):
    n=int(input())
    if n<=1:
        print(n)
        continue
    a=[[1,1],[1,0]]
    b=[[1],[0]]
    # 多用于递推中
    ans=mul(ksm(a,n-1),b)
    ans=ans[0][0]
    print(ans)
